package com.mid;

import java.util.Arrays;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 根据后续和中序遍历构造树
 * @date 2022/8/27 17:56
 */
public class Demo106 {

    /**
     * Definition for a binary tree node.
     * */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
       return build(inorder,postorder);
    }

    private TreeNode build(int[] inorder, int[] postorder) {
        if(postorder.length<=0){
            return null;
        }
        if(postorder.length==1){
            return new TreeNode(postorder[0]);
        }
        int rootValue = postorder[postorder.length - 1];
        TreeNode root=new TreeNode(rootValue);
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i]==rootValue){
                int[] leftInOrder= Arrays.copyOfRange(inorder,0,i);
                int[] leftPostOrder=Arrays.copyOfRange(postorder,0,i);
                int[] rightInOrder= Arrays.copyOfRange(inorder,i+1,inorder.length);
                int[] rightPosOrder= Arrays.copyOfRange(postorder,i,inorder.length-1);
                root.left=build(leftInOrder,leftPostOrder);
                root.right=build(rightInOrder,rightPosOrder);
                break;
            }
        }
       return root;
    }
}
